/*
 * @lc app=leetcode.cn id=23 lang=java
 *
 * [23] 合并K个升序链表
 */

// @lc code=start
/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode() {}
 *     ListNode(int val) { this.val = val; }
 *     ListNode(int val, ListNode next) { this.val = val; this.next = next; }
 * }
 */
class Solution {
    /**
     * 133/133 cases passed (1 ms)
    Your runtime beats 100 % of java submissions
    Your memory usage beats 72.31 % of java submissions (43.2 MB)
     */
    public ListNode mergeKLists(ListNode[] lists) {
        if (lists == null || lists.length == 0)
            return null;
        int len = lists.length;
        if (len == 1)
            return lists[0];
        return merge(lists, 0, len - 1);
    }

    private ListNode merge(ListNode[] lists, int l, int r) {
        if (l == r)
            return lists[l];
        int mid = (l + r) / 2;
        if (mid == l) {
            return mergeTwoLists(lists[l], lists[r]);
        } else {
            return mergeTwoLists(merge(lists, l, mid), merge(lists, mid + 1, r));
        }
    }

    public ListNode mergeTwoLists(ListNode a, ListNode b) {
        ListNode dummy = new ListNode(0);
        ListNode cur = dummy;
        while (a != null && b != null) {
            if (a.val < b.val) {
                cur.next = a;
                cur = cur.next;
                a = a.next;
            } else {
                cur.next = b;
                cur = cur.next;
                b = b.next;
            }
        }
        if (a != null) {
            cur.next = a;
        } else if (b != null) {
            cur.next = b;
        }
        return dummy.next;
    }
}
// @lc code=end
